/*
 * @lc app=leetcode.cn id=63 lang=cpp
 *
 * [63] 不同路径 II
 */

// @lc code=start
class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        //不同路径升级版 加了障碍物
        //dp[i][j]代表到达(i,j)的路径条数
        //递归方程dp[i][j]=dp[i-1][j]+dp[i][j-1]
        //初始化 因为只能往右和往下 所以上边界和左边界可以初始化为1
        //但注意的是如果有障碍物 后面全0
        vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(),0));
        bool isobstac = false; //是否有障碍物
        for (int i = 0; i < obstacleGrid.size(); i++)
        {
            if (obstacleGrid[i][0] == 1)
            {
                isobstac = true;
            }
            if (!isobstac)
            {
                dp[i][0] = 1;
            }
            else
            {
                dp[i][0] = 0;
            }
        }
        isobstac = false;
        for (int j = 0; j < obstacleGrid[0].size(); j++)
        {
            if (obstacleGrid[0][j] == 1)
            {
                isobstac = true;
            }
            if (!isobstac)
            {
                dp[0][j] = 1;
            }
            else
            {
                dp[0][j] = 0;
            }
        }
        //初始化完毕
        for (int i = 1; i < obstacleGrid.size(); i++)
        {
            for (int j = 1; j < obstacleGrid[0].size(); j++)
            {
                if (obstacleGrid[i][j] == 1)
                {
                    dp[i][j] = 0;
                }
                else
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};
// @lc code=end
